package com.yvon.service.demo.algorithm.offer;


import java.util.Collections;
import java.util.PriorityQueue;

/**
 * 最小的k个数
 * 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
 * https://doocs.gitee.io/leetcode/#/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9840.%20%E6%9C%80%E5%B0%8F%E7%9A%84k%E4%B8%AA%E6%95%B0/README
 */
public class P40 {

    public static void main(String[] args) {
        Solution solution = new P40().new Solution();
        int[] arr = {1,4,9,3,2,6,8,5};
        int[] leastNumbers = solution.getLeastNumbers(arr, 4);
        for (int i = 0; i < leastNumbers.length; i++) {
            System.out.print(leastNumbers[i] + " ");
        }
    }


    class Solution {
        public int[] getLeastNumbers(int[] arr, int k) {
            if (k == 0) {
                return new int[]{};
            }
            PriorityQueue<Integer> bigRoot = new PriorityQueue<>(k, Collections.reverseOrder());
            for (int e : arr) {
                if (bigRoot.size() < k) {
                    bigRoot.offer(e);
                }else if (e < bigRoot.peek()) {
                    bigRoot.poll();
                    bigRoot.offer(e);
                }
            }
            int[] res = new int[k];
            for (int i = 0; i < k; ++i) {
                res[i] = bigRoot.poll();
            }
            return res;
        }
    }
}
